package com.leetcode.geek;

/**
 * Description: 极客时间
 * 数据结构与算法之美专栏
 * 40 动态规划
 * Date: 2019/8/28 8:47 上午
 *
 * @author zkingcobra
 */
public class DynamicProgramming {

    /**
     * 递归备忘录的代码
     */
    static class RecursionSnippet {

        private int mMinValue = Integer.MIN_VALUE; // 结果放到 maxW 中
        // 物品重量
        private int[] weight = {
                2, 2, 4, 6, 3
        };
        // 物品个数
        private int n = 5;
        // 背包承受的最大重量
        private int w = 9;
        // 备忘录,默认值 false
        private boolean[][] mem = new boolean[5][10];

        public static void main(String[] args) {

        }

        /**
         * 调用 f(0, 0)
         */
        public void f(int i, int cw) {
            // cw==w 表示装满了,i==n 表示物品都考察完了
            if (cw == w || i == n) {
                if (cw > mMinValue) {
                    mMinValue = cw;
                }
                return;
            }
            // 重复状态
            if (mem[i][cw]) {
                return;
            }
            // 记录 (i, cw) 这个状态
            mem[i][cw] = true;
            // 选择不装第 i 个物品
            f(i + 1, cw);
            if (cw + weight[i] <= w) {
                // 选择装第 i 个物品
                f(i + 1, cw + weight[i]);
            }
        }
    }

    /**
     * 动态规划的片段，
     */
    class DynamicProgrammingSnippet {

        /**
         * 二维数组的方式
         *
         * @param weight 物品重量
         * @param n 物品个数
         * @param w 背包可承载重量
         */
        public int knapsack(int[] weight, int n, int w) {
            boolean[][] states = new boolean[n][w + 1]; // 默认值 false
            states[0][0] = true;  // 第一行的数据要特殊处理，可以利用哨兵优化
            if (weight[0] <= w) {
                states[0][weight[0]] = true;
            }
            for (int i = 1; i < n; ++i) { // 动态规划状态转移
                for (int j = 0; j <= w; ++j) {// 不把第 i 个物品放入背包
                    if (states[i - 1][j]) {
                        states[i][j] = states[i - 1][j];
                    }
                }
                for (int j = 0; j <= w - weight[i]; ++j) {// 把第 i 个物品放入背包
                    if (states[i - 1][j]) {
                        states[i][j + weight[i]] = true;
                    }
                }
            }
            for (int i = w; i >= 0; --i) { // 输出结果
                if (states[n - 1][i]) {
                    return i;
                }
            }
            return 0;
        }
    }
}
